package listbyorder.access101_200.test130;

import java.util.HashSet;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/9 23:33
 */
public class Solution1 {

    // 方法一； DFS内搜
    // 从里面的‘O’元素开始搜索，如果碰到了边界就结束，否则将此位置上的元素改为'X'
    public void solve(char[][] board) {
        int rows = board.length;
        if (rows == 0) {
            return;
        }
        int cols = board[0].length;
        //考虑除去边界以外的所有 O
        for (int i = 1; i < rows - 1; i++) {
            for (int j = 1; j < cols - 1; j++) {
                if (board[i][j] == 'O') {
                    //visited 用于记录 DFS 过程中已经访问过的节点
                    HashSet<String> visited = new HashSet<>();
                    //如果没有到达边界，就把当前 O 置为 X
                    if (!solveHelper(i, j, board, visited)) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }

    private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited) {
        //是否访问过
        if (visited.contains(row + "@" + col)) {
            return false;
        }
        visited.add(row + "@" + col);

        //到达了 X 直接返回 false
        if (board[row][col] == 'X') {
            return false;
        }

        if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1)     {
            return true;
        }

        //分别尝试四个方向
        if (solveHelper(row - 1, col, board, visited)
                || solveHelper(row, col - 1, board, visited)
                || solveHelper(row + 1, col, board, visited)
                || solveHelper(row, col + 1, board, visited)) {
            return true;
        } else {
            return false;
        }
    }

}
